package may;

import java.util.HashSet;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-18 20:14
 * @description：
 * @modified By：
 * @version:
 */
public class May18 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/continuous-subarray-sum/solution/lian-xu-de-zi-shu-zu-qiu-he-by-lenn123/
     * 对于子数组 nums[i:j]nums[i:j] (不包含下标 j )，其区间和为 sum[j] - sum[i]sum[j]−sum[i] (其中 sum 为预处理得到的前缀和数组)，
     * sum[2] 数组 0+1 下标的和 3 = 0+1+2 的和
     * 由于我们需要控制子数组长度大于等 2，因此每次计算出的 sum[j]\%ksum[j]%k 的值，
     * 我们不能立即放入字典中，而是引入一个中间变量 cachecache 缓存我们的值，
     * 待下一次计算时再加入字典，以保证满足条件的子数组长度至少为 2。
     * 我们要判断的是 (sum[j] - sum[i])\%k(sum[j]−sum[i])%k 是否等于 0。
     * 根据 modmod 运算的性质，我们知道 (sum[j] - sum[i])\%k = sum[j]\%k - sum[i]\%k(sum[j]−sum[i])%k=sum[j]%k−sum[i]%k。
     * 故若想 (sum[j] - sum[i])\%k = 0(sum[j]−sum[i])%k=0，则必有 sum[j]\%k = sum[i]\%ksum[j]%k=sum[i]%k
     *这里其实就是数学题了
     *
     * create time: 2020-5-18 20:34
     * @params [nums, k]
     * @return boolean
     */
    public boolean checkSubarraySum(int[] nums, int k) {
        int N = nums.length, cache = 0;
        int[] sum = new int[N+1];
        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < N; i++) {
            sum[i+1] = sum[i] + nums[i];
            int res = k == 0 ? sum[i+1] : sum[i+1] % k; //k==0特殊判断 记录这次的取余
            if (set.contains(res)) return true; //如果
            set.add(cache);
            cache = res; //记录这次的取余的值 在下一次的循环加入set
        }

        return false;
    }
    /**
     * create by: 冯涛滔
     * description: 中心扩散法(下面介绍动态规划) https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/
     * 总结:
     * 从字符串的每一个字符开始 从当前位置的两边开始找和中间一样的字符 找到没有为止,
     * 然后左右一起扩散 因为中间是一样的字符只要左右两边都相等就是回文字了 记录下最长回文字的长度和位置
     * create time: 2020-5-18 20:53
     * @params [s]
     * @return java.lang.String
     */
    public String longestPalindrome1(String s) {

        if (s == null || s.length() == 0) {
            return "";
        }
        int strLen = s.length();
        int left = 0;
        int right = 0;
        int len = 1;
        int maxStart = 0;
        int maxLen = 0;

        for (int i = 0; i < strLen; i++) {
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                len++;
                left--;
            }
            while (right < strLen && s.charAt(right) == s.charAt(i)) {
                len++;
                right++;
            }
            while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {
                len = len + 2;
                left--;
                right++;
            }
            if (len > maxLen) {
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);

    }
    /**
     * create by: 冯涛滔
     * description:动态规划版 https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/
     * 我们用一个 boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[l][r]=true，
     * 我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符，是不是减少了很多重复计算。
     * 进入正题，动态规划关键是找到初始状态和状态转移方程。
     * 初始状态，l=r 时，此时 dp[l][r]=true。
     * 状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。
     * create time: 2020-5-18 21:04
     * @params [s]
     * @return java.lang.String
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
//                r-L 不是1
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) { //左右值相同并且 中间的字符串是回文字
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);

    }



}
